/*
 * @lc app=leetcode.cn id=212 lang=golang
 *
 * [212] 单词搜索 II
 */

// @lc code=start
// 此处使用字典保存前缀，但可以使用前缀树对于前缀进行保存
func findWords(board [][]byte, words []string) []string {
	tmpTrie := make(map[string]bool) //用于缓存前缀以及是否为单词
	for _, v := range words {
		for i := 1; i <= len(v); i++ {
			if i == len(v) {
				tmpTrie[v] = true
			} else {
				if _, ok := tmpTrie[v[:i]]; !ok {
					tmpTrie[v[:i]] = false
				}
			}
		}
	}

	m, n := len(board), len(board[0])
	res := make([]string, 0)
	isVisit := make([][]bool, m)
	for i, _ := range isVisit {
		isVisit[i] = make([]bool, n)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if _, ok := tmpTrie[string(board[i][j])]; ok {
				tmp := ""
				Words(&board, &isVisit, i, j, m, n, &tmpTrie, &tmp, &res)
			}
		}
	}
	return res
}

func Words(board *[][]byte, isVisit *[][]bool, i, j, m, n int, tmpTrie *map[string]bool, tmp *string, res *[]string) {
	if i < 0 || i >= m || j < 0 || j >= n {
		return
	}
	if (*isVisit)[i][j] == true {
		return
	}
	(*isVisit)[i][j] = true
	*tmp = *tmp + string((*board)[i][j])
	// fmt.Println(*tmp)
	if v, ok := (*tmpTrie)[(*tmp)]; ok {
		if v == true {
			v := *tmp
			*res = append(*res, v)
			(*tmpTrie)[*tmp] = false
		}
		Words(board, isVisit, i-1, j, m, n, tmpTrie, tmp, res)
		Words(board, isVisit, i+1, j, m, n, tmpTrie, tmp, res)
		Words(board, isVisit, i, j-1, m, n, tmpTrie, tmp, res)
		Words(board, isVisit, i, j+1, m, n, tmpTrie, tmp, res)
	}
	*tmp = (*tmp)[:len(*tmp)-1]
	(*isVisit)[i][j] = false
	return
}

// @lc code=end
